package com.zhj.interview;

import java.util.*;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveTask;

public class Test16 {

    public static void main(String[] args) throws ExecutionException, InterruptedException {
        int[] bigArr = new int[10000000];
        for (int i = 0; i < 10000000; i++) {
            bigArr[i] = (int) (Math.random() * 80000);
        }
        ForkJoinPool forkJoinPool = new ForkJoinPool();
        MyForkJoinTask task = new MyForkJoinTask(bigArr);
        long start = System.currentTimeMillis();
        forkJoinPool.submit(task).get();
        long end = System.currentTimeMillis();
        System.out.println("耗时：" + (end-start));
    }

}
class MyForkJoinTask extends RecursiveTask<int[]> {

    private int source[];

    public MyForkJoinTask(int source[]) {
        if (source == null) {
            throw new RuntimeException("参数有误！！！");
        }
        this.source = source;
    }

    @Override
    protected int[] compute() {
        int l = source.length;
        if (l < 2) {
            return Arrays.copyOf(source, l);
        }
        if (l == 2) {
            if (source[0] > source[1]) {
                int[] tar = new int[2];
                tar[0] = source[1];
                tar[1] = source[0];
                return tar;
            } else {
                return Arrays.copyOf(source, l);
            }
        }
        if (l > 2) {
            int mid = l / 2;
            MyForkJoinTask task1 = new MyForkJoinTask(Arrays.copyOf(source, mid));
            task1.fork();
            MyForkJoinTask task2 = new MyForkJoinTask(Arrays.copyOfRange(source, mid, l));
            task2.fork();
            int[] res1 = task1.join();
            int[] res2 = task2.join();
            int tar[] = merge(res1, res2);
            return tar;
        }
        return null;
    }

    private int[] merge(int[] res1, int[] res2) {
        int l1 = res1.length;
        int l2 = res2.length;
        int l = l1 + l2;
        int tar[] = new int[l];
        for (int i = 0, i1 = 0, i2 = 0; i < l; i++) {
            int v1 = i1 >= l1 ? Integer.MAX_VALUE : res1[i1];
            int v2 = i2 >= l2 ? Integer.MAX_VALUE : res2[i2];
            // 如果条件成立，说明应该取数组array1中的值
            if(v1 < v2) {
                tar[i] = v1;
                i1++;
            } else {
                tar[i] = v2;
                i2++;
            }
        }
        return tar;
    }
}
